package leetcode.editor.cn.dsa23_graph;
//给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
// 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
//
// 示例: 
// X X X X
//X O O X
//X X O X
//X O X X
// 
// 运行你的函数后，矩阵变为：
// X X X X
//X X X X
//X X X X
//X O X X
// 
// 解释:
// 被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被
//填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 
// 👍 440 👎 0

public class SurroundedRegions130 {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 解题思路：
         * 只要和边界相连的O(包括边界O)都不算被围绕，保持不变
         * 除此之外其他的O都是被围绕的区域，需要填充为'X'
         * 遍历每个边界节点，找出边界节点为O的以及和边界相连的O节点，做一个标记
         * 遍历所有节点，有标记的还原为O，本身为O的替换为X
         */
        int m, n;
        public void solve(char[][] board) {
            // 对每个边界节点进行dfs处理
            // 处理第一行和最后一行节点
            m = board.length;
            if (m == 0) return;
            n = board[0].length;
            for (int i = 0; i < n; i++) {
                dfs(board, 0, i);
                dfs(board, m - 1, i);
            }
            // 处理第一列和最后一列节点，其中四个顶点已经被处理
            for (int i = 1; i < m - 1; i++) {
                dfs(board, i, 0);
                dfs(board, i, n - 1);
            }
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    char c = board[i][j];
                    if (c == 'A') { // 标记为A的重新替换为O
                        board[i][j] = 'O';
                    } else if(c == 'O') { // 标记为O的需要替换为X
                        board[i][j] = 'X';
                    }
                }
            }
        }

        // 标记dfs路径上相连的'O'
        public void dfs(char[][] board, int x, int y) {
            // 越界或者当前节点不是'O'，则递归结束
            if (x < 0 || y < 0 || x >= m || y >= n
                    || board[x][y] != 'O') return;
            // 对相连的'O'进行标记
            board[x][y] = 'A';
            dfs(board, x - 1, y); // 扩展当前节点的上邻接点
            dfs(board, x + 1, y); // 扩展当前节点的下邻接点
            dfs(board, x, y - 1); // 扩展当前节点的左邻接点
            dfs(board, x, y + 1);// 扩展当前节点的右邻接点
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}